
/*
* Copyright 2010, Center for Advanced Information Systems,Nanyang Technological University
*
* File name: SimVerify.java
*
* Abstract: Verify the similarity between two graphs by the MCS
*
* Current Version:      0.1
* Auther:               Jin Changjiu
* Modified Date:        Aug.17,2010
*
*/
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package gblend.similarity;

/**
 *
 * @author cjjin
 */

import gblend.adjlistgraph.ALGraph;
import java.util.Vector;
import gblend.frequentindex.Vertex;
import gblend.infrequentindex.Nodecompare;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;

public class SimVerify {

    private Vector<Integer> matchednodeset = null;
    private Vector<Vertex> qnodes = new Vector<Vertex>();

    public SimVerify(ALGraph q)
    {
        for(int i = 0;i<q.getNnum();i++)
        {
            q.getNode(i).setId(i);
            qnodes.addElement(q.getNode(i));
        }
        Nodecompare nc = new Nodecompare();//sort the nodes by label and degree
        Collections.sort(qnodes,nc);
    }

    //the main verification mathod
    public  boolean verify(ALGraph q, ALGraph g, int missed)
    {
        matchednodeset = new Vector<Integer>();
        Vector<Vertex> gnodes = new Vector<Vertex>();
        for(int i = 0;i<g.getNnum();i++)
        {
            g.getNode(i).setId(i);
            gnodes.addElement(g.getNode(i));
        }

        Nodecompare nc = new Nodecompare();//sort the nodes by label and degree
        Collections.sort(gnodes,nc);

        for(int i = 0;i<qnodes.size();i++)
        {
            Vertex tmpq = qnodes.elementAt(i);
           
            for(int j = 0;j<gnodes.size();j++)
            {
                Vertex tmpg = gnodes.elementAt(j);
                //randomly choose two nodes
                Vector<Integer> neighborset1 = tmpq.getIn();
                Vector<Integer> neighborset2 = tmpg.getIn();
                if(tmpq.getDegree()-missed<=tmpg.getDegree()
                   && tmpq.getLabel().equals(tmpg.getLabel())
                  && neighborCampatible2(q, g, neighborset1, neighborset2, missed))//8.23
                {
                    State s = new State();//create new state(qnode,gnode)
                    s.setM1(tmpq.getId());
                    s.setM2(tmpg.getId());

                   if(match(q, g, s, missed))//match is a recursion function
                   {
                        return true;
                   }
                }//end if
            }
       }

    return false;
 
 }

    
public void getNeighbors(Vector<Integer>M, Vertex node)
{
     node.getM().clear();

     Vector<Integer> indegree = node.getIn();//the neighbors of nodei in q
     for(int i = 0; i< indegree.size(); i++)
     {
        if(M.contains(indegree.elementAt(i)))
        {
           node.setM(indegree.elementAt(i));//neighbors in M1
        }
     }
}

// the parent node of i, j, which are already in M and campatible
 public boolean neighborCampatible(ALGraph q, ALGraph g,State s, Vertex node1, Vertex node2, int missed)
 {
       getNeighbors(s.getM1(), node1);
       getNeighbors(s.getM2(), node2);
      
       int m = 0;
       for(int i = 0; i< node1.getM().size(); i++)
       {
         for(int j = 0; j< node2.getM().size(); j++)
         {
             //if there are campatible pair among the neighbors of nodei and nodej
             if(q.getNode(node1.getM().elementAt(i)).getLabel().equals(g.getNode(node2.getM().elementAt(j)).getLabel())
             && q.getNode(node1.getM().elementAt(i)).getDegree()-missed<= g.getNode(node2.getM().elementAt(j)).getDegree())
             {
                      m++;
             }
         }
       }
       // all the neighbors of node1 in M can find the matched neighbors of node2 in M
       if(m>=node1.getM().size())
       {
            return true;
       }
       else
       {
            return false;
       }

 }


 // the parent node of i, j, which are already in M and campatible
 public boolean neighborCampatible2(ALGraph q, ALGraph g, Vector<Integer> neighborset1, Vector<Integer> neighborset2, int missed)
 {
      
      HashSet<Integer> matchedSet = new HashSet<Integer>();

       for(int i = 0; i< neighborset1.size(); i++)
       {
         int id1 = neighborset1.elementAt(i);
         HashSet<Integer> matched = new HashSet<Integer>();
         for(int j = 0; j< neighborset2.size(); j++)
         {
             int id2 = neighborset2.elementAt(j);
             //if there are campatible pair among the neighbors of nodei and nodej
             if(q.getNode(id1).getLabel().equals(g.getNode(id2).getLabel())
             && q.getNode(id1).getDegree()-missed<= g.getNode(id2).getDegree())
             { 
                matched.add(id2);
             }
         }
         if(matched.isEmpty())
         {
             return false;
         }
         else
         {
            matchedSet.addAll(matched);
         }
       }
       // all the neighbors of node1 in M can find the matched neighbors of node2 in M
       if(matchedSet.size()>=neighborset1.size())
       {
            return true;
       }
       else
       {
            return false;
       }
       
   }
  
  //nodes compatible
    public boolean compatible(State state, Pair pair, ALGraph q, ALGraph g, int missed)
    {
        int id1= pair.getM();
        int id2 = pair.getN();

        boolean f1 = !state.getM1().contains(id1) && !state.getM2().contains(id2)
                && q.getNode(id1).getLabel().equals(g.getNode(id2).getLabel())
                && q.getNode(id1).getDegree()-missed<= g.getNode(id2).getDegree();
               
        boolean f2 = neighborCampatible(q, g, state, q.getNode(id1), g.getNode(id2), missed);
        if(f1 && f2)
        {
            return true;
        }
        else
        {
            return false;
        }

    }


   public  void getRule(ALGraph g, Vector<Integer> in, Vector<Integer> M)
   {
        //all the input nodes which not in M
        for(int i = 0;i<M.size();i++)
        {
            //get Tin
            Vector<Integer> allin = g.getNode(M.elementAt(i)).getIn();
            for(int j = 0; j< allin.size();j++)
            {
                if(!M.contains(allin.elementAt(j)))
                {
                     in.addElement(allin.elementAt(j));
                }
            }
        }
  }

  //construct the Pair
public Vector<Pair> constructP(ALGraph q, ALGraph g, State s, int missed)
{
     Vector<Pair> p = new Vector<Pair>();
     getRule(q, s.getTin1(), s.getM1());
     getRule(g, s.getTin2(), s.getM2());

     if(!s.getTin1().isEmpty()&&!s.getTin2().isEmpty())
     {
       for(int i = 0; i< s.getTin1().size();i++)
       {
           int id1 = s.getTin1().elementAt(i);
          for(int j = 0; j< s.getTin2().size();j++)
          {
             int id2= s.getTin2().elementAt(j);
             if(q.getNode(id1).getDegree()-missed<=g.getNode(id2).getDegree()
              &&q.getNode(id1).getLabel().equals(g.getNode(id2).getLabel()))
            {
                 Pair tmp = new Pair();
                 tmp.setM(id1);
                 tmp.setN(id2);
                 if(!pairContain(p,tmp))
                 { 
                    p.addElement(tmp);
                 }
             }
           }
       }
    }
  //order the q's nodes in pair vector, choose the one has more neighbors in M
   return p;
}


public boolean pairContain(Vector<Pair> pairset, Pair pair)
{
    for(int i = 0; i< pairset.size(); i++)
    {
        if(pairset.elementAt(i).getM()==pair.getM() && pairset.elementAt(i).getN()==pair.getN())
            return true;
    }

    return false;

}


    
 //The initialize of P and M
 public  boolean match(ALGraph q, ALGraph g, State state, int missed)
 {
      //calculate the number of edge in matched subgraph of g
      Vector<Integer> IdsetM2 = state.getM2();
      Vector<Integer> IdsetM1 = state.getM1();
      for(int t1=0; t1< IdsetM1.size(); t1++)
      {
          for(int t2=t1+1; t2< IdsetM1.size(); t2++)
          {
           
              if(q.getEdge(IdsetM1.elementAt(t1), IdsetM1.elementAt(t2))>0)
              {
                  if(g.getEdge(IdsetM2.elementAt(t1), IdsetM2.elementAt(t2))>0)
                  {
                        state.addEdgeNumber();//add one edge
                  }
                  else
                  {
                        break;
                  }
              }
          }
      }
      
      int stateEdgenum = state.getEdgeNumber();
     
      if(stateEdgenum ==(q.getEnum()-missed) )
      {
         //get the matched node set
         for(int i =0; i< IdsetM2.size(); i++)
         {
             matchednodeset.addElement(IdsetM2.elementAt(i)); //the position id
          }

         return true;
      }
      else
      {
        //construct the new candidate Pair and get the information of current state
         Vector<Pair> p =  constructP(q,g,state,missed);

         for(Iterator itr=p.iterator(); itr.hasNext();)
         {
            State newstate = new State();
            //store the previous state, by copying the previous states M1 and M2
            for(int j=0;j < state.getM1().size();j++)
            {
                newstate.setM1(state.getM1().elementAt(j));
                newstate.setM2(state.getM2().elementAt(j));
            }
            Pair tmpp = (Pair)itr.next();
                    
            if(compatible(state,tmpp,q,g,missed))//if the new two nodes compatible
            {
               newstate.setM1(tmpp.getM());//add this new pair
               newstate.setM2(tmpp.getN());
       
               if(match(q,g,newstate,missed))// call match again
               {
                  return true;
               }
            }
        }
          
    }

      return false;

 }

public Vector<Integer> getNodeset()
{
        return matchednodeset;
}


}
